//请你设计一个数据结构，支持 添加新单词 和 查找字符串是否与任何先前添加的字符串匹配 。 
//
// 实现词典类 WordDictionary ： 
//
// 
// WordDictionary() 初始化词典对象 
// void addWord(word) 将 word 添加到数据结构中，之后可以对它进行匹配 
// bool search(word) 如果数据结构中存在字符串与 word 匹配，则返回 true ；否则，返回 false 。word 中可能包含一些 '
//.' ，每个 . 都可以表示任何一个字母。 
// 
//
// 
//
// 示例： 
//
// 
//输入：
//["WordDictionary","addWord","addWord","addWord","search","search","search","se
//arch"]
//[[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
//输出：
//[null,null,null,null,false,true,true,true]
//
//解释：
//WordDictionary wordDictionary = new WordDictionary();
//wordDictionary.addWord("bad");
//wordDictionary.addWord("dad");
//wordDictionary.addWord("mad");
//wordDictionary.search("pad"); // return False
//wordDictionary.search("bad"); // return True
//wordDictionary.search(".ad"); // return True
//wordDictionary.search("b.."); // return True
// 
//
// 
//
// 提示： 
//
// 
// 1 <= word.length <= 500 
// addWord 中的 word 由小写英文字母组成 
// search 中的 word 由 '.' 或小写英文字母组成 
// 最调用多 50000 次 addWord 和 search 
// 
// Related Topics 设计 字典树 回溯算法 
// 👍 191 👎 0

package com.leetcode.editor.cn;

//Java：添加与搜索单词 - 数据结构设计
class P211DesignAddAndSearchWordsDataStructure {
    public static void main(String[] args) {
        WordDictionary wordDictionary = new P211DesignAddAndSearchWordsDataStructure().new WordDictionary();
        wordDictionary.addWord("bad");
        wordDictionary.addWord("dad");
        wordDictionary.addWord("mad");
        System.out.println(wordDictionary.search("pad")); // return True

    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class WordDictionary {

        TrieNode root;

        /**
         * Initialize your data structure here.
         */
        public WordDictionary() {
            root = new TrieNode();
        }

        /**
         * Adds a word into the data structure.
         */
        public void addWord(String word) {
            char[] chars = word.toCharArray();
            TrieNode curr = root;
            for (int i = 0; i < chars.length; i++) {
                if (curr.child[chars[i] - 'a'] == null) {
                    curr.child[chars[i] - 'a'] = new TrieNode();
                }
                curr = curr.child[chars[i] - 'a'];
            }
            curr.isWord = true;
        }

        /**
         * Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter.
         */
        public boolean search(String word) {
            return searchHelp(word, root);
        }

        private boolean searchHelp(String word, TrieNode root) {
            char[] array = word.toCharArray();
            TrieNode cur = root;
            for (int i = 0; i < array.length; i++) {
                if(array[i] == '.'){// 对于. , 递归的判断所有不为空的孩子
                    for(int j = 0;j < 26; j++){//遇到'.', 则搜索后续的字符子串是否存在
                        if(cur.child[j] != null){
                            if(searchHelp(word.substring(i + 1),cur.child[j])){
                                return true;// 后续的字符子串存在，返回true
                            }
                        }
                    }
                    return false;// 后续的字符子串不存在，返回false
                }
                if (cur.child[array[i] - 'a'] == null) {
                    return false;
                }
                cur = cur.child[array[i] - 'a'];
            }
            return cur.isWord;
        }
    }

    public class TrieNode {
        private final int SIZE = 26;
        TrieNode[] child;
        //当前元素是否是单词的结尾
        boolean isWord;

        public TrieNode() {
            this.child = new TrieNode[SIZE];
            isWord = false;
        }

    }
/**
 * Your WordDictionary object will be instantiated and called as such:
 * WordDictionary obj = new WordDictionary();
 * obj.addWord(word);
 * boolean param_2 = obj.search(word);
 */
//leetcode submit region end(Prohibit modification and deletion)

}